/*
 *用结点n中数码到目标所需要移动的步数作为选择策略，优先选择离目标状态更近的节点进行分支
 */
#include "TEight.h"
#include "TList.h"
#include <iostream>
#include <cmath>
using namespace std;
#define X 3
#define MAX 100000
class NearestBFS:public TEight
{
private :
	int cost;
	bool repeat(TList<NearestBFS> &L) {
		int n = L.Getlen();
		for (int i = 0; i < n; i++)
			if (L.GetData(i) == *this)
				return true;;
		return false;
	}
	void printl(TList<NearestBFS> &L) {
		NearestBFS T = *this;
		if (T.last == -1)
			return;
		else {
			T = L.GetData(T.last);
			T.printl(L);
			T.printSelf();
		}
	}
	int getCost()//得到cost值
	{
		for(int i=1;i<=Num; i++)
		  if( target[i]!=0 )
			for(int j=1;j<=Num;j++)
			{
				if( target[i] ==origin[j] )
				{
					int dis = abs(j-i);
					cost += dis / X;
					cost += dis % X;
					break;
				}
			}
		return cost;
	}
	NearestBFS getNextState(int head,int tail,TList<NearestBFS> &tList)
	{
		int leastCost = MAX;
		int father = -1;
		NearestBFS t ;
		t.setSpace(-1);
		while(head <= tail)
		{
		 for(int direction=0;direction<DirNum ; direction++)
		 {
			 NearestBFS tBFS = tList.GetData(head);
		//	 if(tBFS.hasExpand == true)
			//	 break;//last不为-1，说明已经
			 if(tBFS.extend(direction) && tBFS.repeat(tList)==false)
			 {
				 int numPosition = tBFS.getLastSpace();//被移动数字的当前位置
				 int lastNumPosition = tBFS.getSpace();//被移动数字的前一状态的位置
				 int j;
				 for(j=1; j<=Num; j++)
					 if(target[j] == tBFS.origin[numPosition])
						 break;
				 int curDis = abs(numPosition - j);
				 int lastDis = abs(lastNumPosition - j);

				 int curCost =  curDis/X + curDis%X;//在当前状态target[j]移动的代价
				 int lastCost = lastDis/X + lastDis%X;//在前一状态target[j]移动的代价

				 int tempCost = tBFS.cost + curCost - lastCost +1;

				 if(tempCost < leastCost)
				 {
					 leastCost = tempCost;
					 father = head;
					 t = tBFS;
				 }
			 }
		 }
		 head ++;
		}

		 if(leastCost == MAX)
			 return t;
		 else
		 {
			 t.cost = leastCost;
			 t.last = father;
			 return t;
		 }
	}
public :
	NearestBFS(int * _orgin, int *_target):TEight(_orgin,_target)
	{
		cost = 0;
		cost = getCost();
		cout<<"初始代价为："<<cost<<endl;
	}
	NearestBFS()
	{
	}

	virtual void search()
	{
		 NearestBFS tBFS = *this;
		 TList<NearestBFS> tList;
		 tList.Append(tBFS);//初始状态入队列

		 int head =0,tail=0;
		 while(head <= tail)
		 {
			tBFS = getNextState(head, tail, tList);
			if (tBFS.getSpace() <= 0)//space<=0说明无法打到下一状态
				break;

			tList.Append(tBFS);
			//tBFS.hasExpand = true;
			tail++;

			if (tBFS.isFind() == true)
			{
				//找到了
				cout << "find!" << endl;
				tBFS.printl(tList);
				tBFS.printSelf();
				return;
			}
		 }
		 cout<<"无解！"<<endl;
	}
};


